#include <iostream>
#include <string>

using namespaces::std;

struct RELSULT {
	int length;
	string str[20];
};

string sorce[18][2] = {
	{"left sock",	"pants"},
	{"pants",	"belt"},
	{"suit jacket",	"left shoe"},
	{"suit jacket",	"right shoe"},
	{"left shoe",	"overcoat"},
	{"right sock",	"pants"},
	{"right shoe",	"overcoat"},
	{"t-shirt",	"suit jacket"},
	{"t-shirt",	"dress shirt"},
	{"dress shirt",	"pants"},
	{"dress shirt",	"suit jacket"},
	{"tie",		"suit jacket"},
	{"pants",	"suit jacket"},
	{"belt",	"suit jacket"},
	{"suit jacket",	"overcoat"},
	{"dress shirt",	"tie"},
	{"suit jacket",	"sun glasses"},
	{"sun glasses",	"overcoat"}
};

class DepAnalyze
{
public:
	DepAnalyze();
	~DepAnalyze();

	int StartAnalyze();
	int Output();

private:
	int write_in_rel(int line, string sorce[][], int i, int j);
	int find_same(string clothe, int i);
private:
	int m_rel_line
	struct RELSULT m_rel[20];
};

DepAnalyze::DepAnalyze()
{
}

DepAnalyze::~DepAnalyze()
{
}

/*
 * This function is used to serch the m_rel[], if sorce[i][j] has been in m_rel[], it stores the other string to m_rel[].
 * Return values: 0--write the other string in rel right; 1--the other string has been in m_rel[]; -1--sorce[i][j] doesn't exist in m_rel[].
 * */
int DepAnalyze::write_in_rel(int line, string sorce, int i, int j)
{
	int m,n;
	for(m=0; m<line; m++)
	{
		for(n=0; n<m_rel[m].length; n++)
		{
			if(strcmp(m_rel[m].str[n], sorce[i][j]) == 0)
			{
				if(j == 0)
				{

					int k;
					for(k=0; k<m_rel[m+1].length; k++)
					{
						if(strcmp(m_rel[m+1].str[k], sorce[i][j+1]) == 0)
						{
							return 1;
						}
						if(k == (m_rel[m+1].length-1))
						{
							strcpy(m_rel[m+1].str[length++], sorce[i][j+1]);
							return 0;
						}
					}	       
				}else{
					int k;
					for(k=0; k<m_rel[m-1].length; k++)
					{
						if(strcmp(m_rel[m-1].str[k], sorce[i][j-1]) == 0)
						{
							return 1;
						}
						if(k == (m_rel[m-1].length-1))
						{
							strcpy(m_rel[m-1].str[length++], sorce[i][j-1]);
							return 0;
						}
					}
				}
			}
		}
	}

	return -1;
}

/*This function is used to serch interrelated string with sorce[i][j] followed, if had, write in m_rel[].
 * The return value err: 0--the following don't have the same string with sorce[i][j];
 * 			 1--the same string has been found and wrote in m_rel[];
 * 			 -1--the same string has been found but it does't exist in m_rel[]. */
int DepAnalyze::find_same(string clothe, int i)
{
	int m,n;
	int err=0;

	for(m=i+1; m<18; m++)
	{
		for(n=0; n<2; n++)
		{
			if(strcmp(clothe, sorce[m][n]) == 0)
			{
				if(write_in_rel(m_rel_line, sorce, m, n) == -1)
				{
					printf("Ooo, there is something error, %s doesn't exist in m_rel[]!\n", sorce[m][n]);
					err=-1;
				}
				err=1;
			}
		}
	}
	return err;
}

int DepAnalyze::StartAnalyze()
{
	strcpy(m_rel[m_rel_line++].str[length++], sroce[0][0]);

	int i,j;
	for(i=0; i<18; i++)
	{
		for(j=0; j<2; j++)
		{
			if(write_in_rel(m_rel_line, sorce, i, j) == -1)
			{
				printf("Ooo, there is something error, %s doesn't exist in m_rel[]!\n", sorce[i][j]);
			}

			if(find_same(sorce[i][j], i) == -1)
			{
				printf("Ooo, there is something erroe, %s has another same string, but it does't exist in m_rel[]!\n", sorce[i][j]);
			}

		}
	}
}

int DepAnalyze::Output()
{
	for(i=0; i<m_rel_line; i++)
	{
		for(j=0; j< m_rel[i].length; j++)
		{
			printf("%s", m_m_rel[i][j]);
		}
		printf("\n");
	}

	return 0;
	
}

int call()
{
	DepAnalyze depAnalyze;
	depAnalyze.StartAnalyze();
	depAnalyze.Output();
}
